#include <ctype.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

bool canPartition(int* nums, int numsSize);

int main()
{
	return 0;
}

bool canPartition(int* nums, int numsSize)
{
	int sum = 0;
	for (int i = 0; i < numsSize; i++) sum += nums[i];

	if (sum & 1) return false;
	int target = sum >> 1;
	char bag[target + 1]; memset(bag, 0, sizeof(bag));
	bag[0] = 1;

	for (int i = 0; i < numsSize; i++) {
		int cur = nums[i];
		for (int j = target; j >= cur; j--)
			if (bag[j - cur]) bag[j] = 1;
	}

	return bag[target];
}
